package com.wp.targetOffer;

/**
 * Created by 王萍 on 2017/8/14 0014.
 */

/**
 * 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，
 * 另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。
 */
public class 复杂链表的复制 {
    public static void main(String[] args) {

        RandomListNode node1 = new RandomListNode(1);
        RandomListNode node2 = new RandomListNode(2);
        RandomListNode node3 = new RandomListNode(3);
        RandomListNode node4 = new RandomListNode(4);
        RandomListNode node5 = new RandomListNode(5);
        RandomListNode node6 = new RandomListNode(6);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;

        node1.random = node3;
        node2.random = node4;
        node3.random = node2;
        node4.random = node6;
        node5.random = node4;
        node6.random = node5;
    }

    public static RandomListNode Clone(RandomListNode pHead) {
        if (pHead == null) return null;
        RandomListNode firstHead = pHead;
        RandomListNode newHead = null;
        while (firstHead != null) {
            RandomListNode q = new RandomListNode(firstHead.label);
            q.next = firstHead.next;
            firstHead = firstHead.next;
        }
        return newHead;
    }

    private static class RandomListNode {
        int label;
        RandomListNode next = null;
        RandomListNode random = null;

        RandomListNode(int label) {
            this.label = label;
        }
    }
}
